package madixin.t239;

import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {

    //优先队列
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length < k) {
            return null;
        }
        int[] res = new int[nums.length - k + 1];
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < k; i++) {
            queue.add(nums[i]);
        }
        res[0] = queue.peek();

        for (int i = 1; i < res.length ; i++) {
            queue.remove(nums[i-1]);
            queue.add(nums[i + k -1]);
            res[i] = queue.peek();
        }
        return res;
    }

    //暴力
    public int[] maxSlidingWindow1(int[] nums, int k) {
        if (nums.length < k) {
            return null;
        }
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < res.length; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i + k; j++) {
                max = Math.max(max, nums[j]);
            }
            res[i] = max;
        }
        return res;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3));
//        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2-o1;
//            }
//        });
//
//        queue.add(5);
//        queue.add(2);
//        queue.add(10);
//
//
//        System.out.println(queue.peek());
//        System.out.println(queue.peek());

    }
}